package suanfa;

public class QuickSort3 {
	private QuickSort3(){}
	
	private static void sort(Comparable[] arr,int l,int r){
		if(r-l<=15){
			InsertionSort.sort(arr,l,r);
			return;
		}
		swap(arr,l,(int)(Math.random()*(r-l+1))+l);
		Comparable v=arr[l];
		int lt = l;     // arr[l+1...lt] < v
        int gt = r+1; // arr[gt...r] > v
        int i = l+1;    // arr[lt+1...i) == v
        while( i < gt ){
            if( arr[i].compareTo(v) < 0 ){
                swap( arr, i, lt+1);
                i ++;
                lt ++;
            }
            else if( arr[i].compareTo(v) > 0 ){
                swap( arr, i, gt-1);
                gt --;
            }
            else{ // arr[i] == v
                i ++;
            }
        }

        swap( arr, l, lt );

        sort(arr, l, lt-1);
        sort(arr, gt, r);
		
	}
	
	
	private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
	
	public static void sort(Comparable[] arr){
		int n=arr.length;
		sort(arr,0,n-1);
		
	}
	public static void main(String[] args) {
		int N = 1000000;
		Comparable[]a={0,10,6,8,9,58,2,3,1,0,23,1658,25,658,56,22,21,0,20,22,23};
		sort(a);
		for(int i=0;i<a.length;i++){
			System.out.println(a[i]);
		}

        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("suanfa.QuickSort3", arr);
        Comparable[] arr2={1,5,6,84,15,26,355,26,35,36,45,5,36,45,18,4,44,58};
		QuickSort3 qs=new QuickSort3();
		long startTime = System.currentTimeMillis();
		qs.sort(arr2);
	    long endTime = System.currentTimeMillis();
		
		for(int i=0;i<a.length;i++){
			System.out.println(a[i]);
		}
		System.out.println("cost:" + (endTime - startTime) + "ms");

		for(Comparable e:arr2){
			 System.out.print(e+" ");
			 }
		 System.out.println();
        return;

	}

}
